package jianzhi_offer;

public class _51_正则表达式匹配 {
    public static void main(String[] args) {
        _51_正则表达式匹配 test = new _51_正则表达式匹配();
        System.out.println(test.match("aaa".toCharArray(),"ab*ac*a".toCharArray()));
    }

    public boolean match(char[] str, char[] pattern) {
        boolean dp[][] = new boolean[str.length+1][pattern.length+1];
        dp[0][0] = true;
        //dp[i][j] 表示 str[i]与pattern[j]是否匹配
        for(int i=1;i<pattern.length;++i){
            //很重要 这样开头的*就能完全匹配了 不考虑有**
            if(pattern[i] == '*' && dp[0][i-1]) {
                dp[0][i+1] = true;
            }
        }
        for(int i=0;i<str.length;++i){
            for(int j=0;j<pattern.length;++j){
                if(pattern[j] == '.' || pattern[j] == str[i]){
                    dp[i+1][j+1] = dp[i][j];
                }else if(pattern[j] == '*'){
                    if(str[i] != pattern[j-1] && pattern[j-1] != '.'){
                        dp[i+1][j+1] = dp[i+1][j-1];//这个可以忽略掉了
                    }else{//否则相等 或者 全部可以匹配
                        dp[i+1][j+1] = dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1];
                    }
                }
            }
        }
        return dp[str.length][pattern.length];
    }

    public boolean isMatch(String s, String p) {
        if(s==null||p==null) return false;
        boolean [][]dp=new boolean[s.length()+1][p.length()+1];
        //dp[i][j]表示第s中第i个字符和p中第j个字符匹配
        dp[0][0]=true;
        char []chars1=s.toCharArray();
        char []chars2=p.toCharArray();
        //不考虑**的情况
        for(int i=1;i<chars2.length;++i) {
            if(chars2[i]=='*'&&dp[0][i-1]) {
                dp[0][i+1]=true;
            }
        }
        for(int i=0;i<chars1.length;++i) {
            for(int j=0;j<chars2.length;++j) {
                if(chars2[j]=='.'||chars2[j]==chars1[i]) {
                    dp[i+1][j+1]=dp[i][j];
                }
                else if(chars2[j]=='*') {
                    if(chars2[j-1]!=chars1[i]&&chars2[j-1]!='.') {
                        //*之前的字符匹配不上
                        dp[i+1][j+1]=dp[i+1][j-1];
                    }
                    else {
                        dp[i+1][j+1]=(dp[i+1][j]||dp[i][j+1]||dp[i+1][j-1]);
                    }
                }
            }
        }
        return dp[chars1.length][chars2.length];
    }
}
